package beust;

/**
 * Finds base n numbers whose digits don't repeat. Solution to Cedric's coding
 * challenge: http://beust.com/weblog/archives/000491.html
 * 
 * Ever so slightly modified version of Bob's
 * http://crazybob.org/FastBeustSequence.java.html
 *
 * @author Bob Lee (crazybob@crazybob.org)
 * @author Jonathan Hawkes (blog.techhead.biz)
 */
public class ModifiedBeustSequence {

  public static void countTo(long max, int base, Listener listener) {
    Digit digits = Digit.set(base);
    Digit before1 = digits.next; // Numbers begin with 1
    try { // For base 10, count to 9, then 98, then 987...
      for (int powerOfBase=1; powerOfBase <= base; powerOfBase++) {
        count(before1, digits, base, powerOfBase, 0, max, listener);
      }
    } catch (SequenceTerminator theEnd) {
        // max exceeded
    }
  }

  /**
   * Called recursively for each digit from most to least significant.
   *
   * @param before the digit before the first digit to count,
   *               used to skip 0 for most significant digit
   * @param digits the set of digits,
   *               the first digit being a non-digit (-1) that
   *               points to the head of the set
   * @param powerOfBase 1 is the rightmost digit, 2 is to the left of 1, etc.
   * @param highOrderPart these are the more significant digits in the number
   * @param max don't count past this
   * @param listener hears results
   * @throws SequenceTerminator when max is exceeded
   */
  private static void count(Digit before, Digit digits,
          int base, int powerOfBase, long highOrderPart, long max,
          Listener listener) throws SequenceTerminator {
    for (Digit digit = before.next; digit != null; digit = digit.next) {
      long number = highOrderPart + digit.value;
      if (powerOfBase == 1) { // the last (rightmost) digit in the number
        if (number > max)
          throw new SequenceTerminator();
        listener.hear(number);
      } else { // still in high order digits
        before.next = digit.next; // Temporarily take this digit out
        count(digits, digits, base, powerOfBase-1, number*base, max, listener);
        before.next = digit; // Put the digit back into comission
        before = digit;
      }
    }
  }
  
  /** A digit, part of a SINGLY-linked set. */
  static class Digit {

    static Digit set(int base) {
      return new Digit(-1, base);
    }

    private Digit(int v, int base) {
      value = v;
      if (v < base-1) next = new Digit(v+1, base);
    }
    
    final int value;
    Digit next;
  }
  
  static class SequenceTerminator extends Throwable {}
}
